/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GodK
 * Date: 2024-03-26
 * Time: 13:44
 */
public class Test {
    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode partition(ListNode head, int x) {
        if(head==null)return null;
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (as == null) {
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae=ae.next;
                }
            } else {
                if (bs == null) {
                    bs = be = cur;
                } else {
                    be.next = cur;
                    be=be.next;
                }
            }
            cur = cur.next;
        }
        if(as==null){
            return bs;
        }
        as.next = bs;
        if(bs!=null){
            be.next=null;
        }
        return as;
    }
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(-1);
        ListNode head = cur;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1=l1.next;
                cur=cur.next;
            }else{
                cur.next = l2;
                l2=l2.next;
                cur=cur.next;
            }
        }
        if(l1==null){
            cur.next=l2;
        }
        if(l2==null){
            cur.next=l1;
        }
        return head.next;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null)return head;
        ListNode n1 = head;
        ListNode n2 = null;
        ListNode n3 = head.next;
        while(n1 != null){
            n1.next = n2;
            n2 = n1;
            n1 = n3;
            if(n3 != null)
                n3 = n3.next;
        }
        return n2;
    }
    public ListNode FindKthToTail (ListNode head, int k) {
        if(k<0 || head == null)return null;
        int count = 0;
        ListNode fast = head;
        ListNode slow = head;
        while(count != k-1){
            fast = fast.next;
            count++;
            if(fast == null)
                return null;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
